﻿using System;
using System.Collections.Generic;
using System.ComponentModel.DataAnnotations;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.CodeTop
{
    public class Solution32
    {
        //这个函数的作用是找多少个括号（（））这种，题目要求连续（）（）
        public int LongestValidParentheses2(string s)
        {


            //左括号的数量大于右括号就可以组成一对
            int len = s.Length;

            if (len < 2)
            {
                return 0;
            }
            int[] dp = new int[len];
            int left = 0;

            if (s[0] == '(')
            {
                left++;
            }

            dp[0] = 0;

            for (int i = 1; i < len; i++)
            {
                if (s[i] == '(')
                {
                    left++;
                    dp[i] = dp[i - 1];
                }
                else//右括号才有可能,而且保证右括号在后面
                {




                    if (left > 0)
                    {
                        dp[i] = dp[i - 1] + 2;
                        left--;
                    }
                    else
                    {
                        dp[i] = dp[i - 1];
                    }
                }

                Console.WriteLine("left   " + left + " dp[i] " + dp[i]);


            }


            return dp[len - 1];

        }
        public int LongestValidParentheses3(string s)
        {



            int len = s.Length;

            if (len < 2)
            {
                return 0;
            }
            int[] dp = new int[len];
            int max = 0;

            dp[0] = 0;
            //每两个字符检测一次，这个字符必须是）
            //这两个字符的情况有四种
            //有效两种
            //  情况 1, ()
            //  情况 2, ))
            //无效两种
            //  情况 3, ((
            //  情况 4, )(
            for (int i = 1; i < len; i++)
            {
                if (s[i] == '(')
                {

                    //dp[i] = 0;
                }
                else//右括号才有可能,而且保证右括号在后面
                {
                    if (s[i - 1] == '(')//情况 1, ()
                    {
                        if (i == 1)//i=1=),i-1=0=(
                        {
                            dp[i] = 2;
                        }
                        else
                        {
                            dp[i] = dp[i - 2] + 2;
                        }



                    }
                    else //  情况 2, ))
                    {
                        //  情况 2, ))，这种情况，先看dp[i-1]是不是有效子串，是的话，dp[i-1]子串之前是不是可以匹配的（
                        //也就是s[i-dp[i-1]-1]=='(',这个时候子串长度加上'('之前的长度dp[i - dp[i - 1] - 2]
                        //也就是这种情况,x()),看x是不是（，但是(之前也可能是另一个组合

                        //由于把左括号dp都设置为0 ，
                        if (dp[i - 1] > 0)
                        {

                            if (i - 1 - dp[i - 1] >= 0)
                            {
                                if (s[i - 1 - dp[i - 1]] == '(')//x==0
                                {
                                    if (i - 2 - dp[i - 1] >= 0) //但是(之前也可能是另一个组合
                                    {

                                        dp[i] = dp[i - 2 - dp[i - 1]] + dp[i - 1] + 2;

                                    }
                                    else
                                    {
                                        dp[i] = dp[i - 1] + 2;
                                    }




                                }
                                else
                                {
                                    dp[i] = 0;
                                }
                            }




                        }

                    }




                }

                Console.WriteLine("left   " + i + " dp[i] " + dp[i]);

                max = Math.Max(max, dp[i]);
            }


            return max;

        }

        //栈
        public int LongestValidParentheses4(string s)
        {

            Stack<int> leftStack = new Stack<int>();

            int len = 0;
            int max = 0;
            leftStack.Push(-1);
            for (int i = 0; i < s.Length; i++)
            {

                Console.WriteLine("count" + leftStack.Count);

                if (s[i] == ')')
                {
                    leftStack.Pop();
                    if (leftStack.Count > 0)
                    {

                        len = i - leftStack.Peek();//长度是当前的右括号减去上一个没有匹配的右括号

                    }
                    else
                    {
                        leftStack.Push(i);//没有匹配的右括号
                    }

                    max = Math.Max(max, len);


                }
                else
                {
                    leftStack.Push(i);

                }
                Console.WriteLine(max);
            }
            return max;


        }

        //计算数量
        public int LongestValidParentheses(string s)
        {
            //左括号的数量大于右括号就可以组成一对
            int len = s.Length;

            if (len < 2)
            {
                return 0;
            }

           
          
            int curlen = 0;
            int max = 0;
            int left = 0;
            int right = 0;


            for (int i = 0; i < len; i++)
            {
                if (s[i] == '(')
                {
                    left++;

                }
                else
                {
                    right++;
                }

                if (right == left)
                {

                    curlen = 2 * left;
                    max = Math.Max(max, curlen);

                }
                if (right > left)
                {

                    left = 0;
                    right = 0;

                }

            }
           left = 0;
            right = 0;


            for (int i = len-1; i >= 0; i--)
            {
                if (s[i] == '(')
                {
                    left++;

                }
                else
                {
                    right++;
                }

                if (right == left)
                {

                    curlen = 2 * left;
                    max = Math.Max(max, curlen);

                }
                if (right <left)
                {

                    left = 0;
                    right = 0;

                }

            }
            return max;
        }



    }
    class Program32
    {
        static void Main32(string[] args)
        {

            string s = ")()())";
            Solution32 solution = new Solution32();
            int res = solution.LongestValidParentheses(s);
            Console.WriteLine(res);
        }
    }
}
